/****************
*PID:
*Auth:Jonariguez
*****************
*/
#define lson k*2,l,m
#define rson k*2+1,m+1,r
#define rep(i,s,e) for(i=(s);i<=(e);i++)
#define For(j,s,e) For(j=(s);j<(e);j++)
#define sc(x) scanf("%d",&x)
#define In(x) scanf("%I64d",&x)
#define SS(x,y) scanf("d",&x,&y)
#define pf(x) printf("%d",x)
#define pfn(x) printf("%d\n",(x))
#define Pf(x) printf("%I64d",(x))
#define Pfn(x) printf("%I64d\n",(x))
#define Pc printf(" ")
#define PY puts("YES")
#define PN puts("NO")
#define MP make_pair
#define X first
#define Y second
#define PI acos(-1.0)
#include <stdio.h>
#include <string.h>
#include <string>
#include <math.h>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
typedef int Ll;
Ll quick_pow(Ll a,Ll b,Ll MOD){a%=MOD;Ll res=1;while(b){if(b&1)res=(res*a)%MOD;b/=2;a=(a*a)%MOD;}return res;}

const int maxn=200000+10;
const int MOD=10001;

int v[maxn];

void Exgcd(int a,int b,int &d,int &x,int &y){
    if(b==0){
        d=a;x=1;y=0;return ;
    }
    Exgcd(b,a%b,d,y,x);
    y-=x*(a/b);
}

int n;

bool ok(int a,int b){
    for(int i=1;i<=n*2;i++){
        if(i%2==0){
            v[i]=(a*v[i-1]+b)%MOD;
            v[i]+=MOD;v[i]%=MOD;
        }else {
            if(i==1) continue;
            int temp=(a*v[i-1]+b)%MOD;
            temp+=MOD;temp%=MOD;
            if(temp!=v[i]) return false;
        }
    }
    return true;
}


int main()
{
    int i,j;
    scanf("%d",&n);
    for(i=1;i<=n*2;i+=2)
        scanf("%d",&v[i]);
    int a,b;
    int yes=0;
    for(a=0;a<=10000;a++){
        int temp=((a*a)%MOD*v[1])%MOD;
        int c=((v[3]-temp)%MOD+MOD)%MOD;
        int x,y,d;
        Exgcd(a+1,10001,d,x,y);
        if(c%d) continue;
        int t=10001/d;
        x=((x*(c/d))%t+t)%t;
        b=x;
        b%=MOD;
        if(b<0) b+=MOD;
        if(ok(a,b)){
            yes=1;break;
        }
    }
    if(yes)
        for(i=2;i<=n*2;i+=2) printf("%d\n",v[i]);
    return 0;
}



